// un test
#include <algorithm>
#include <vector>

struct bipartite_graph
{
	typedef int size_type;
	typedef std::vector<size_type> edge_type;
	typedef std::vector<size_type>::iterator edge_iter;
	typedef std::vector<edge_type> graph_type;

	bipartite_graph(size_type n) // [0, n)
								 // for even node black, {0, 2, 4, ...}
								 //      odd node white, {1, 3, 5, ...}
	{
		graph.resize(n);
		linked.resize(n);
		visited.resize(n);
	}

	void add_edge(size_type x, size_type y)
	{
		graph[x].push_back(y); graph[y].push_back(x);
	}

	bool hungarian_dfs(size_type u)
	{
		for (edge_iter it = graph[u].begin(); it != graph[u].end(); ++it) {
			size_type v = *it;
			if (visited[v]) continue;
			visited[v] = true;
			if (linked[v] == -1 || hungarian_dfs(linked[v])) {
				linked[u] = v; linked[v] = u;
				return true;
			}
		}
		return false;
	}

	size_type max_match()
	{
		size_type n = graph.size();
		std::fill(linked.begin(), linked.end(), -1);
		size_type bi_match = 0;
		for (size_type i = 0; i < n; i += 2) {
			std::fill(visited.begin(), visited.end(), false);
			if (hungarian_dfs(i)) bi_match++;
		}
		return bi_match;
	}

private:
	graph_type graph;
	edge_type linked;
	std::vector<bool> visited; // FIXME
};

